//
//  BinarySearchTree.swift
//  AlgorithmProgram
//
//  Created by jianghongbao on 2020/4/14.
//  Copyright © 2020 Bruce Jiang. All rights reserved.
//

import UIKit


/// Definition for a binary tree node.
public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

class BinarySearchTree: NSObject {
    /// 面试题55 - I. 二叉树的深度
    /*
     输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
     
     例如：
     
     给定二叉树 [3,9,20,null,null,15,7]，
     3
     / \
     9  20
     /  \
     15   7
     返回它的最大深度 3 。
     
     来源：力扣（LeetCode）
     链接：https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof
     著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    
    func maxDepth(_ root: TreeNode?) -> Int {
        if let _root = root {
            return max(maxDepth(_root.left),maxDepth(_root.right)) + 1
        }else {
            return 0
        }
    }
    
    /// 面试题27. 二叉树的镜像
    /*
     请完成一个函数，输入一个二叉树，该函数输出它的镜像。
     
     例如输入：
     
          4
        /   \
       2     7
      / \   / \
     1   3 6   9
     镜像输出：
     
          4
        /   \
       7     2
      / \   / \
     9   6 3   1
     
     来源：力扣（LeetCode）
     链接：https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof
     著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    func mirrorTree(_ root: TreeNode?) -> TreeNode? {
        if let _root = root {
            let temp: TreeNode? = mirrorTree(_root.left)
            _root.left = mirrorTree(_root.right)
            _root.right = temp
            return _root
        }
        return nil
    }
    
    /// 617. 合并二叉树
    /*
   给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

    你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

    示例 1:

    输入:
        Tree 1                     Tree 2
              1                         2
             / \                       / \
            3   2                     1   3
           /                           \   \
          5                             4   7
    输出:
    合并后的树:
             3
            / \
           4   5
          / \   \
         5   4   7
    注意: 合并必须从两个树的根节点开始。

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/merge-two-binary-trees
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */ 
    func mergeTrees(_ t1: TreeNode?, _ t2: TreeNode?) -> TreeNode? {
        if t1 == nil && t2 == nil { return nil }
        let realVal: Int = (t1?.val ?? 0) + (t2?.val ?? 0)
        let ret: TreeNode = TreeNode.init(realVal)
        ret.left = mergeTrees(t1?.left, t2?.left)
        ret.right = mergeTrees(t1?.right, t2?.right)
        return ret
    }
    
    ///226. 翻转二叉树 -> 同: 面试题27. 二叉树的镜像
    /*
    翻转一棵二叉树。

    示例：

    输入：

         4
       /   \
      2     7
     / \   / \
    1   3 6   9
    输出：

         4
       /   \
      7     2
     / \   / \
    9   6 3   1

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/invert-binary-tree
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    */
    func invertTree(_ root: TreeNode?) -> TreeNode? {
        if let _root = root {
            let temp: TreeNode? = mirrorTree(_root.left)
            _root.left = mirrorTree(_root.right)
            _root.right = temp
            return _root
        }
        return nil
    }
    
    /*
    如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

    只有给定的树是单值二叉树时，才返回 true；否则返回 false。
    示例 1：#imageLiteral(resourceName: "singleBInarySearchTree_sample_1")
    输入：[1,1,1,1,1,null,1]
    输出：true

    示例 2：#imageLiteral(resourceName: "singleBInarySearchTree_sample_2")
    输入：[2,2,2,5,2]
    输出：false
    
    提示：
    给定树的节点数范围是 [1, 100]。
    每个节点的值都是整数，范围为 [0, 99] 。
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/univalued-binary-tree/
    */
    func isUnivalTree(_ root: TreeNode?) -> Bool {
        if let _root = root {
            let ret: Bool = true
            if _root.left == nil && _root.right == nil { return ret }
            var tempArray: [TreeNode?] = [root?.left, root?.right]
            while !tempArray.isEmpty {
                for temp in tempArray {
                    if let _temp = temp {
                        if _temp.val != _root.val {
                            return false
                        }
                    }
                }
                var newTempArray: [TreeNode?] = []
                for temp in tempArray {
                    if !(temp?.left == nil && temp?.right == nil) {
                        newTempArray.append(temp?.left)
                        newTempArray.append(temp?.right)
                    }
                }
                tempArray = newTempArray
            }
            return ret
        }
        return false
    }
    
    /// 669. 修剪二叉搜索树
    /*
    给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。

    示例 1:

    输入:
        1
       / \
      0   2

      L = 1
      R = 2

    输出:
        1
          \
           2
    示例 2:

    输入:
        3
       / \
      0   4
       \
        2
       /
      1

      L = 1
      R = 3

    输出:
          3
         /
       2
      /
     1

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/trim-a-binary-search-tree
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    */
    func trimBST(_ root: TreeNode?, _ L: Int, _ R: Int) -> TreeNode? {
        if let _root = root {
            if (_root.val > R) {
                return trimBST(root?.left, L, R)
            }
            if (_root.val < L) {
                return trimBST(root?.right, L, R)
            }
        }else {
            return root
        }
        root?.left = trimBST(root?.left, L, R)
        root?.right = trimBST(root?.right, L, R)
        return root
    }
    
    /*
     538. 把二叉搜索树转换为累加树
    给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

     

    例如：

    输入: 原始二叉搜索树:
                  5
                /   \
               2     13

    输出: 转换为累加树:
                 18
                /   \
              20     13

     

    注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/convert-bst-to-greater-tree
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
    var currentTotal: Int = 0
    func convertBST(_ root: TreeNode?) -> TreeNode? {
        if root == nil {
            return nil
        }
        root?.right = convertBST(root?.right)
        currentTotal += root?.val ?? 00
        root?.val = currentTotal
        root?.left = convertBST(root?.left)
        return root
    }
}
